CORDIC units are employed for example in synchronizing devices of modems for the standards IEEE 802.11(a) and Hyperlan/2. In such synchronizing devices on-line calculations of the arc tan function and complex multiplications of data, using the sine and the cosine function are necessary.
The mode of operation of CORDIC units is based on the CORDIC algorithm. The CORDIC algorithm is an algorithm for efficiently computing various transcendental and geometrical functions. Examples of such functions which can be computed directly by means of the CORDIC algorithm are geometrical and arithmetic multiplication, division operations, the sine and cosine function, the root function, the inverse tangent, the inverse hyperbolic tangent, the hyperbolic sine and the hyperbolic cosine. Those basic functions can be used for computing further functions, for example logarithms. An essential feature of the conventional CORDIC algorithm is that it can be implemented as a recursive method in which rotation is approximated by a series of forward and reverse rotations through fixedly predetermined elementary angles. Those forward and reverse rotations, referred to hereinafter for brevity as elementary rotations, can be embodied by adding, subtracting, shift and table operations. Thus the CORDIC algorithm can be embodied in the form of a CORDIC unit, for example a digital CORDIC processor, which only needs to include adders/subtractors, shifters and reference tables, but for example no real digital multiplier.
CORDIC units compute from three input values x0, y0 and z0 three output values x1, y1 and z1, wherein x0 and y0 are the co-ordinates of the vector to be rotated and z0 is the rotational angle through which the rotation occurs, which is to be approximated by the CORDIC algorithm. The CORDIC algorithm can either be effected in such a way that y1 tends towards zero (vectoring mode) or that z1 tends towards zero (rotation mode). Each of those two modes can be used in polar co-ordinates, hyperbolic co-ordinates or linear co-ordinates.
In the conventional CORDIC algorithm the angular range of the rotary angles which can be approximated is limited to a given range, the convergence range. That convergence range is given in the conventional CORDIC algorithm by the angular interval [−99.9°, 99.9°]. So that y1 or z1 can tend towards zero |tan−1(y0/x0| or |z0| must be in the convergence range, that is to say less than or equal to 99.9°.
In addition upon a rotation through an elementary angle in the conventional CORDIC algorithm the length of the rotated vector is not constant. Thus, for each elementary rotation there is a factor by which the length of the vector changes. Those changes in length must be taken into consideration by a scaling factor in the output values x1 and y1. The scaling factor is a constant if the CORDIC process is always carried out using all implemented elementary rotations.
Furthermore the CORDIC algorithm is slow to execute by virtue of its iterative nature.
In order to enlarge the limited convergence range of the CORDIC algorithm, J. S. Walther, “A Unified Algorithm for Elementary Functions”, Proc. Joint Spring Comput. Conf., vol 36, pages 379-385, July 1971, proposed using mathematical identities to subject the input values x0, y0 and z0 to a pre-processing operation. That procedure is known as the “argument reduction process”. Admittedly such mathematical identities actually help when overcoming the limited convergence range but they are unwieldy for hardware uses by virtue of the necessary processing time and expenditure.
A further approach for overcoming the limited convergence range is described for example in J. M. Delosme, “VLSI Implementation of Rotations in Pseudo-Euclidean Spaces”, Proc. ICASSP, vol 2, pages 927-930. That approach requires the repetition of given iteration steps. In dependence on how the iteration steps to be repeated are determined, many such iteration steps to be repeated may be necessary in order to achieve a result with the desired level of accuracy. However, with the number of iteration steps to be repeated, the processing time required for that purpose also increases. In addition, in that approach the scaling factor is not a constant as the number of iteration steps and thus the number of elementary rotations to be effected is not constant.
Therefore the object of the present invention is to provide a CORDIC unit which is improved over conventional CORDIC units.
A further object of the invention is to provide a pre-processing unit for a CORDIC unit, with which the angular range for the rotary angle to be actually calculated by the CORDIC unit can be reduced.